package graph;

import java.util.*;

/**
 * 图
 *
 */
public class Graph {
    // 顶点 存储 节点
    List<String> dingDian;
    // 存储边 之间关系 二维数组 表示链接
    int[][] bian;
    //边的个数 关系数目
    int bianCount;

    boolean[] bfsActive;

    public Graph(int size){
        dingDian = new ArrayList<>(size);
        bian = new int[size][size];
        bianCount = 0;
        bfsActive = new boolean[size];
    }

    /**
     * 顶点
     * @param item
     */
    public void addItem(String item){
        dingDian.add(item);
    }

    /**
     * 添加 边之间关系
     * @param a
     * @param b
     */
    public void addBian(String a,String b,int weight){
       if(dingDian.contains(a) && dingDian.contains(b)){
           bian[dingDian.indexOf(a)][dingDian.indexOf(b)] = weight;
           bian[dingDian.indexOf(b)][dingDian.indexOf(a)] = weight;
       }
       return;
    }



    /**
     * 深度 优先遍历
     * 思路：
     * 当你第一次开始访问的时候 需要记录第一个值
     * 然后从第一行开始找临近点，找到且判断有木有被放入 若没 则放入 并且
     * 从被放入的那个行 去找临近的放入
     * @param i 第几行 初始第0行
     * @param res 返回的被访问的值
     * @return
     */
    public List<String> dfs(int i,List<String> res){
        int[] ints = bian[i];
        if(i==0){
            res.add(dingDian.get(0));
        }
        //从所在行进行找 找到 符合条件的 （为嘛 这边用j 递归传 ：这是一个 正方形 二维数组 大小都一样）
        for (int j = 0; j < ints.length; j++) {
            if( ints[j]>0 && !res.contains( dingDian.get(j)) ){
                res.add(dingDian.get(j));
                dfs(j,res);
            }
        }
        return res;
    }

    /**
     *
     * @return 返回广度优先遍历的结果
     */
    public List<String> bfs(){
        //初始化 节点的状态 false 未被访问过
        for (int i = 0; i < bfsActive.length ; i++) {
            bfsActive[i] = false;
        }
        List<String> res = new ArrayList<>();
        bfs(res, new ArrayDeque<>());
        return res;
    }

    /**
     * 1.如果标记为空 则放入队列第一个元素
     * 2.每次都从队列取出一个元素 遍历行 如果有则插入到队列
     * 3.重复 2 队列为空 则退出
     * @param res 返回结果
     * @param queue 队列
     */
    public void bfs(List<String> res,Queue<String> queue){
        //如果全部未被标记 则  需要 往队列 放一个元素
        if(!isEmpty()){
            queue.add(dingDian.get(0));
        }
        //从queue 取出元素 并标记
        if(queue.isEmpty()){
           return;
        }
        String poll = queue.poll();
        int i = dingDian.indexOf(poll);
        res.add(poll);
        bfsActive[i] = true;
        int[] ints = bian[i];
        //访问其 行其他节点 没被访问过直接 放入
        for (int j = 0; j < ints.length ; j++) {
            if(!bfsActive[j] && ints[j]>0){
                if(!queue.contains(dingDian.get(j))){
                    queue.add(dingDian.get(j));
                }
            }
        }
        bfs(res,queue);
    }
    public boolean isEmpty(){
        for (int i = 0; i < bfsActive.length ; i++) {
            if(bfsActive[i]){
                return true;
            }
        }
        return false;
    }




    public static void main(String[] args) {
        Graph graph = new Graph(8);
        graph.addItem("1");graph.addItem("2");graph.addItem("3");graph.addItem("4");graph.addItem("5");
        graph.addItem("6");graph.addItem("7");graph.addItem("8");
        graph.addBian("1","2",1); graph.addBian("1","3",1);
        graph.addBian("2","4",1); graph.addBian("2","5",1);
        graph.addBian("4","8",1);graph.addBian("5","8",1);
        graph.addBian("3","6",1);graph.addBian("3","7",1);
        graph.addBian("6","7",1);
        for (int i = 0; i < graph.bian.length; i++) {
            System.out.println(Arrays.toString(graph.bian[i]));
        }

        List<String> depths = graph.dfs(0, new ArrayList<>());
        System.out.println("深度优先："+depths);

        List<String> a = graph.bfs();
        System.out.println("广度优先"+a);
    }




}
